package 分类.滑动窗口;

import java.util.HashMap;

//返回s中涵盖t所有字符的最小子串
public class 最小覆盖子串 {

    public static String minWindow(String s, String t) {
        HashMap<Character, Integer> need=new HashMap<>();
        HashMap<Character, Integer> window=new HashMap<>();
        int left=0,right=0;
        for (char c:t.toCharArray()){
            int num=need.getOrDefault(c,0);
            need.put(c,++num);
        }
        int vaild=0;
        int len=Integer.MAX_VALUE;
        //取结果和len配合使用
        int start=0;
        while (right<s.length()){
            char c=s.charAt(right);
            //右移窗口
            right++;
            if(need.containsKey(c)){
                int num=window.getOrDefault(c,0);
                window.put(c,++num);
                if(window.get(c)==need.get(c)){
                    vaild++;
                }
            }


            //判断是否要收缩
            while (vaild==need.size()){
                if(right-left<len){
                    start=left;
                    len=right-left;
                }
                char a=s.charAt(left);
                left++;
                if(need.containsKey(a)){
                    //先减少合法数量
                    if(window.get(a)==need.get(a)){
                        vaild--;
                    }
                    int num=window.getOrDefault(a,0);
                    window.put(a,--num);
                }
            }
        }
        return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    }

    public static void main(String[] args) {
        String s="ADOBECODEBANC";
        String t="ABC";
        System.out.println("minWindow(s,t) = " + minWindow(s, t));
    }

}
